package slidingWindow;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class findAnagrams {
    // 法一：固定大小的滑动窗口——基于string和stringBuilder超时
    // 估计是因为频繁的字符串操作O (n*m²)，indexOf和deleteCharAt都是om的时间复杂度
    public static List<Integer> findAnagrams(String s, String p) {
        ArrayList<Integer> list = new ArrayList<>();
        int right = 0;
        for (int left = 0; left <= s.length() - p.length(); left++) {
            // abab ab
            // right为开区间
            right = left + p.length();
            String str = s.substring(left, right);
            StringBuilder subStr = new StringBuilder(str);
            // 遍历p中的每个元素
            for (int j = 0; j < p.length(); j++) {
                int indexOf = str.indexOf(p.charAt(j));
                if (indexOf == -1) {
                    // 不存在
                    continue;
                } else {
                    subStr.deleteCharAt(indexOf);
                    str = subStr.toString();
                }
            }
            if (subStr.length() == 0) {
                list.add(left);
            }
        }
        return list;
    }

    // 法一：固定大小的滑动窗口——基于数组
    // 数组中各个字母的位置确定，定位和删除的时间复杂度都为o1
    // O(m+(n−m)×Σ),Σ为26
    public static List<Integer> findAnagrams2(String s, String p) {
        ArrayList<Integer> list = new ArrayList<>();
        // 初始化目标数组
        // 初始化原数组
        int[] source = new int[26];
        int[] target = new int[26];
        if (p.length()>s.length()) {
            return list;
        }
        for (int i = 0; i < p.length(); i++) {
            target[p.charAt(i) - 'a']++;
            source[s.charAt(i) - 'a']++;
        }
        int right = 0;
        right = p.length() - 1;
        for (int left = 0; left <= s.length() - p.length(); left++, right++) {

            if (Arrays.equals(source, target)) {
                list.add(left);
            }
            if (left != s.length() - p.length()) {
                source[s.charAt(left) - 'a']--;
                source[s.charAt(right + 1) - 'a']++;
            }

        }

        return list;
    }

    public static void main(String[] args) {
        String s = "cbaebabacd", p = "abc";
        // String s = "abab", p = "ab";
        // String s = "aaaa", p = "aa";
        List<Integer> anagrams = findAnagrams2(s, p);
        System.out.println(anagrams);
    }
}
